{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# General Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.wikipedia.org/wiki/Tree_(data_structure)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "#!python -m pip install binarytree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "         _______12_______\n",
      "        /                \\\n",
      "     __9___             __3___\n",
      "    /      \\           /      \\\n",
      "  _7       _2        _1       _6\n",
      " /  \\     /  \\      /  \\     /  \\\n",
      "11   5   10   4    13   0   14   8\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from binarytree import tree\n",
    "\n",
    "my_tree = tree(height=3, is_perfect=True)\n",
    "print(my_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Binary search trees (BST)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Definition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In computer science, a binary search tree, also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a given node with a value, all the nodes in the left sub-tree are less than or equal to the value of that node. Also, all the nodes in the right sub-tree of this node are greater than that of the parent node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "        ______7_______\n",
      "       /              \\\n",
      "    __3__           ___11___\n",
      "   /     \\         /        \\\n",
      "  1       5       9         _13\n",
      " / \\     / \\     / \\       /   \\\n",
      "0   2   4   6   8   10    12    14\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from binarytree import bst\n",
    "\n",
    "my_bst = bst(height=3, is_perfect=True)\n",
    "print(my_bst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "root node\n",
      "left child node\n",
      "left grandchild node\n",
      "1: 1\n",
      "2: 2\n",
      "3: None\n",
      "4: None\n",
      "5: 5\n",
      "6: None\n",
      "7: 7\n",
      "8: None\n",
      "9: 9\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.right_child = None\n",
    "        self.left_child = None\n",
    "\n",
    "class Tree:\n",
    "    def __init__(self):\n",
    "        self.root_node = None\n",
    "\n",
    "    def insert(self, data):\n",
    "        node = Node(data)\n",
    "        if self.root_node is None:\n",
    "            self.root_node = node\n",
    "        else:\n",
    "            current = self.root_node\n",
    "            parent = None\n",
    "            while True:\n",
    "                parent = current\n",
    "                if node.data < parent.data:\n",
    "                    current = current.left_child\n",
    "                    if current is None:\n",
    "                        parent.left_child = node\n",
    "                        return\n",
    "                else:\n",
    "                    current = current.right_child\n",
    "                    if current is None:\n",
    "                        parent.right_child = node\n",
    "                        return\n",
    "\n",
    "    def search(self, data):\n",
    "        current = self.root_node\n",
    "        while True:\n",
    "            if current is None:\n",
    "                return None\n",
    "            elif current.data is data:\n",
    "                return data\n",
    "            elif current.data > data:\n",
    "                current = current.left_child\n",
    "            else:\n",
    "                current = current.right_child\n",
    "\n",
    "n1 = Node(\"root node\")\n",
    "n2 = Node(\"left child node\")\n",
    "n3 = Node(\"right child node\")\n",
    "n4 = Node(\"left grandchild node\")\n",
    "\n",
    "n1.left_child = n2\n",
    "n1.right_child = n3\n",
    "n2.left_child = n4\n",
    "\n",
    "current = n1\n",
    "while current:\n",
    "    print(current.data)\n",
    "    current = current.left_child\n",
    "\n",
    "tree = Tree()\n",
    "tree.insert(5)\n",
    "tree.insert(2)\n",
    "tree.insert(7)\n",
    "tree.insert(9)\n",
    "tree.insert(1)\n",
    "\n",
    "for i in range(1, 10):\n",
    "    found = tree.search(i)\n",
    "    print(\"{}: {}\".format(i, found))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tree traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Depth-first traversal (height first, we normally use it to get max-levels)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To be honest, I don't know anything about the difference between the three sub-method of tree traversal until today.\n",
    "\n",
    "It's surprising to see that the place where we put our print function has a big effect on the result that we can get from a tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### In-order traversal and infix notation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "    __2__\n",
      "   /     \\\n",
      "  1       5\n",
      " / \\     / \\\n",
      "4   3   0   6\n",
      "\n",
      "4 1 3 2 0 5 6 "
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def main(self, root) -> int:\n",
    "        self.travel(root)\n",
    "        \n",
    "    def travel(self, node):\n",
    "        if node is None:\n",
    "            return\n",
    "        self.travel(node.left)\n",
    "        print(node.val, end=\" \")\n",
    "        self.travel(node.right)\n",
    "\n",
    "my_tree = tree(height=2, is_perfect=True)\n",
    "print(my_tree)\n",
    "Solution().main(my_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "    __2__\n",
      "   /     \\\n",
      "  0       4\n",
      " / \\     / \\\n",
      "3   6   1   5\n",
      "\n",
      "[3, 0, 6, 2, 1, 4, 5]\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def main(self, root) -> int:\n",
    "        print(self.travel(root, []))\n",
    "        \n",
    "    def travel(self, node, l):\n",
    "        if node is None:\n",
    "            return []\n",
    "        return self.travel(node.left, l) + [node.val] + self.travel(node.right, l)\n",
    "\n",
    "my_tree = tree(height=2, is_perfect=True)\n",
    "print(my_tree)\n",
    "Solution().main(my_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pre-order traversal and prefix notation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "    __3__\n",
      "   /     \\\n",
      "  5       6\n",
      " / \\     / \\\n",
      "0   4   2   1\n",
      "\n",
      "3 5 0 4 6 2 1 "
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def main(self, root) -> int:\n",
    "        self.travel(root)\n",
    "        \n",
    "    def travel(self, node):\n",
    "        current = node\n",
    "        if current == None:\n",
    "            return\n",
    "        print(current.val, end=\" \")\n",
    "        self.travel(node.left)\n",
    "        self.travel(node.right)\n",
    "\n",
    "my_tree = tree(height=2, is_perfect=True)\n",
    "print(my_tree)\n",
    "Solution().main(my_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Post-order traversal and postfix notation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "    __0__\n",
      "   /     \\\n",
      "  3       5\n",
      " / \\     / \\\n",
      "1   4   2   6\n",
      "\n",
      "1 4 3 2 6 5 0 "
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def main(self, root) -> int:\n",
    "        self.travel(root)\n",
    "        \n",
    "    def travel(self, node):\n",
    "        current = node\n",
    "        if current == None:\n",
    "            return\n",
    "        self.travel(node.left)\n",
    "        self.travel(node.right)\n",
    "        print(current.val, end=\" \")\n",
    "\n",
    "my_tree = tree(height=2, is_perfect=True)\n",
    "print(my_tree)\n",
    "Solution().main(my_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Get paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "    2___\n",
      "   /    \\\n",
      "  8     _5__\n",
      " /     /    \\\n",
      "3     11     9\n",
      "            /\n",
      "           0\n",
      "\n",
      "[2, 8, 3]\n",
      "[2, 5, 11]\n",
      "[2, 5, 9, 0]\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    paths = []\n",
    "    def main(self, root) -> int:\n",
    "        self.paths = []\n",
    "        self.travel(root, [])\n",
    "        \n",
    "    def travel(self, node, l):\n",
    "        if node is None:\n",
    "            return\n",
    "        else:\n",
    "            #print(node.val, end=\" \")\n",
    "            l.append(node.val)\n",
    "            if node.left is None and node.right is None:\n",
    "                self.paths.append(l)\n",
    "                print(l)\n",
    "        self.travel(node.left, l.copy())\n",
    "        self.travel(node.right, l.copy())\n",
    "my_tree = tree(height=3, is_perfect=False)\n",
    "print(my_tree)\n",
    "Solution().main(my_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Breadth-first traversal (width first, we normally use it to get max-width)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> This kind of traversal starts from the root of a tree and visits the node from one level of the tree to the other."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "        _______3________\n",
      "       /                \\\n",
      "    __9___           ____12__\n",
      "   /      \\         /        \\\n",
      "  0       _2       13         6\n",
      " / \\     /  \\     /  \\       / \\\n",
      "1   5   14   7   8    11    4   10\n",
      "\n",
      "[3, 9, 12, 0, 2, 13, 6, 1, 5, 14, 7, 8, 11, 4, 10]\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def main(self, root) -> int:\n",
    "        print(self.travel(root))\n",
    "        \n",
    "    def travel(self, root):\n",
    "        list_of_nodes = []\n",
    "        traversal_queue = deque([root])\n",
    "        \n",
    "        while len(traversal_queue) > 0:\n",
    "            node = traversal_queue.popleft()\n",
    "            list_of_nodes.append(node.val)\n",
    "            \n",
    "            if node.left:\n",
    "                traversal_queue.append(node.left)\n",
    "            \n",
    "            if node.right:\n",
    "                traversal_queue.append(node.right)\n",
    "                \n",
    "        return list_of_nodes\n",
    "                \n",
    "\n",
    "my_tree = tree(height=3, is_perfect=True)\n",
    "print(my_tree)\n",
    "Solution().main(my_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "         ______11_______\n",
      "        /               \\\n",
      "     __1__            ___2___\n",
      "    /     \\          /       \\\n",
      "  _3       8        13       _4\n",
      " /  \\     / \\      /  \\     /  \\\n",
      "14   7   5   6    0    9   12   10\n",
      "\n",
      "[11, '__1__', 1, 2, '__2__', 3, 8, 13, 4, '__3__', 14, 7, 5, 6, 0, 9, 12, 10]\n"
     ]
    }
   ],
   "source": [
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def main(self, root) -> int:\n",
    "        print(self.travel(root))\n",
    "        \n",
    "    def travel(self, root):\n",
    "        list_of_nodes = []\n",
    "        root.level_end = True\n",
    "        traversal_queue = deque([root])\n",
    "        level = 0\n",
    "        \n",
    "        while len(traversal_queue) > 0:\n",
    "            node = traversal_queue.popleft()\n",
    "            list_of_nodes.append(node.val)\n",
    "            \n",
    "            if node.left:\n",
    "                node.left.level_end = False\n",
    "                traversal_queue.append(node.left)\n",
    "            \n",
    "            if node.right:\n",
    "                if node.level_end == True:\n",
    "                    node.right.level_end = True\n",
    "                    level += 1\n",
    "                    list_of_nodes.append(f\"__{level}__\")\n",
    "                else:\n",
    "                    node.right.level_end = False\n",
    "                traversal_queue.append(node.right)\n",
    "                \n",
    "        return list_of_nodes\n",
    "                \n",
    "\n",
    "my_tree = tree(height=3, is_perfect=True)\n",
    "print(my_tree)\n",
    "Solution().main(my_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "  ___1______\n",
      " /          \\\n",
      "4        ____3\n",
      " \\      /     \\\n",
      "  11   14      6\n",
      "         \\      \\\n",
      "          10     5\n",
      "\n",
      "[Node(1)]\n",
      "[Node(4), Node(3)]\n",
      "[Node(11), Node(14), Node(6)]\n",
      "[Node(10), Node(5)]\n",
      "[1, '__2__', 4, 3, '__3__', 11, 14, 6, '__4__', 10, 5]\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def main(self, root) -> int:\n",
    "        print(self.travel(root))\n",
    "        \n",
    "    def travel(self, root):\n",
    "        list_of_vals = []\n",
    "        level_list = [[root]]\n",
    "        \n",
    "        while True:\n",
    "            current_level = level_list[-1]\n",
    "            print(current_level)\n",
    "            level_list.append([])\n",
    "            i = 0\n",
    "            while i < len(current_level):\n",
    "                node = current_level[i]\n",
    "\n",
    "                list_of_vals.append(node.val)\n",
    "\n",
    "                if node.left:\n",
    "                    level_list[-1].append(node.left)\n",
    "\n",
    "                if node.right:\n",
    "                    level_list[-1].append(node.right)\n",
    "                \n",
    "                i += 1\n",
    "            \n",
    "            if len(level_list[-1]) == 0:\n",
    "                break\n",
    "\n",
    "            list_of_vals.append(f\"__{len(level_list)}__\")\n",
    "                \n",
    "        return list_of_vals\n",
    "                \n",
    "\n",
    "my_tree = tree(height=3, is_perfect=False)\n",
    "print(my_tree)\n",
    "Solution().main(my_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "  ______9__\n",
      " /         \\\n",
      "2___        0\n",
      "    \\      / \\\n",
      "    _12   8   4\n",
      "   /           \\\n",
      "  10            13\n",
      "\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def main(self, root) -> int:\n",
    "        print(self.get_nodes_separated_by_levels(root))\n",
    "        \n",
    "    def get_nodes_separated_by_levels(self, root):\n",
    "        if root == None:\n",
    "            return []\n",
    "        \n",
    "        a_list = [root]\n",
    "        b_list = []\n",
    "        switch_flag = 0\n",
    "        level_list = []\n",
    "\n",
    "        while True:\n",
    "            if len(a_list) == 0 and len(b_list) == 0:\n",
    "                break\n",
    "            \n",
    "            if switch_flag == 0:\n",
    "                for node in a_list:\n",
    "                    if node.left:\n",
    "                        b_list.append(node.left)\n",
    "                    if node.right:\n",
    "                        b_list.append(node.right)\n",
    "                level_list.append([n for n in a_list])\n",
    "                a_list = []\n",
    "                switch_flag = 1\n",
    "            else:\n",
    "                for node in b_list:\n",
    "                    if node.left:\n",
    "                        a_list.append(node.left)\n",
    "                    if node.right:\n",
    "                        a_list.append(node.right)\n",
    "                level_list.append([n for n in b_list])\n",
    "                b_list = []\n",
    "                switch_flag = 0\n",
    "        \n",
    "        return level_list\n",
    "\n",
    "my_tree = tree(height=3, is_perfect=False)\n",
    "print(my_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[Node(9)],\n",
      " [Node(2), Node(0)],\n",
      " [Node(12), Node(8), Node(4)],\n",
      " [Node(10), Node(13)]]\n"
     ]
    }
   ],
   "source": [
    "from pprint import pprint as print\n",
    "\n",
    "Solution().main(my_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}